import javax.swing.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wangxin
 * Date: 2024-12-25
 * Time: 19:39
 */
public class MyBtree {
    static class BTreeNode{
         int[] keys;
         int usedSize;
         BTreeNode parent;
         BTreeNode[] subs;
         public BTreeNode(){
             this.keys = new int[M];
             this.subs = new BTreeNode[M+1];
             this.usedSize = 0;
         }
    }
    public static final int M = 3;
    public BTreeNode root;
    public boolean insert(int key){
        if(root == null){
            root = new BTreeNode();
            root.keys[root.usedSize] = key;
            root.usedSize++;
            return true;
        }
       Pair<BTreeNode,Integer> pair = findNode(key);
        if(pair.getVal() != -1){
            return false;
        }
        BTreeNode parent = pair.getKey();
        int index = parent.usedSize -1;
        for(;index >=0;index--){
            if(parent.keys[index] >= key){
                parent.keys[index+1] = parent.keys[index];
            }else{
                break;
            }
        }
        parent.keys[index+1] = key;
          parent.usedSize++;
          if(parent.usedSize < M){
              return true;
          }else{
              split(parent);
              return true;
          }

    }
    public void split(BTreeNode cur){
        BTreeNode newNode = new BTreeNode();
        BTreeNode parent = cur.parent;
        int mid = cur.usedSize >> 1;
        int i = mid+1;
        int j = 0;
        for(;i < cur.usedSize;i++){
            newNode.keys[j] = cur.keys[i];
            newNode.subs[j] = cur.subs[i];
            if(newNode.subs[j]!=null)
            newNode.subs[j].parent = newNode;
            j++;
        }
        newNode.subs[j] = cur.subs[i];
        if(newNode.subs[j]!=null)
            newNode.subs[j].parent = newNode;
        newNode.usedSize=j;
        cur.usedSize = cur.usedSize - j-1;
        newNode.parent = parent;
        if (parent == null){
            root = new BTreeNode();
            root.keys[0] = cur.keys[mid];
            root.subs[0] = cur;
            root.subs[1] = newNode;
            root.usedSize++;
            cur.parent = root;
            newNode.parent = root;
            return;
        }
        int endT = parent.usedSize-1;
        int midVal = cur.keys[mid];

        for(;endT >= 0;endT--){
            if(parent.keys[endT] >= midVal){
                parent.keys[endT+1] = parent.keys[endT];
                parent.subs[endT+2] = parent.subs[endT+1];
            }else{
                break;
            }
        }
        parent.keys[endT+1] = midVal;
        parent.subs[endT+2] = newNode;
        parent.usedSize++;
        if(parent.usedSize>=M){
            split(parent);
        }

    }
    public Pair<BTreeNode,Integer> findNode(int key){
        BTreeNode cur = root;
        BTreeNode parent = null;
        while(cur != null){
            int i = 0;
            while(i < cur.usedSize){
                if(key == cur.keys[i]){
                    return new Pair<>(cur,i);
                }else if(key > cur.keys[i]){
                    i++;
                }else{
                    break;
                }
            }
            parent = cur;
            cur = cur.subs[i];
        }
        return new Pair<>(parent,-1);
    }
    private void inorder(BTreeNode root){
        if(root == null)
            return;
        for(int i = 0; i < root.usedSize; ++i){
            inorder(root.subs[i]);
            System.out.println(root.keys[i]);
        }
        inorder(root.subs[root.usedSize]);
    }

    public static void main(String[] args) {
        MyBtree myBtree = new MyBtree();
        int[] array = {53,139,75,49,145,36,101};
        for (int i = 0;i < array.length;i++){
            myBtree.insert(array[i]);
        }
        myBtree.inorder(myBtree.root);
    }
}

